package Offer;
/*
    剑指 Offer 04. 二维数组中的查找
    在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
    每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样
    的一个二维数组和一个整数，判断数组中是否含有该整数。
* */

import org.junit.Test;

/*
    思路:
        因为行，列都是有序数组
        先对行做一次二分，再对列做一次二分
* */
public class T04_findNumberIn2DArray {
    private int left;
    private int right;

    @Test
    public void test() {
/*        int[][] matrix = {
                        {1, 4, 7, 11, 15},
                        {2, 5, 8, 12, 19},
                        {3, 6, 9, 16, 22},
                        {10, 13, 14, 17, 24},
                        {18, 21, 23, 26, 30}};*/
        int[][] matrix = {
//                {-5}
                {1}, {3}, {5}
        };
        System.out.println(findNumberIn2DArray(matrix, 5));
    }

    //对于题目给出的矩阵，比如右上角的元素，所在行的元素值往左递减，所在列的元素值往下递增
    //借组此特点，从右上角开始遍历，如果当前元素值小于target值，就让i++;
    //如果当前元素值大于target值，就让j--;直到当前元素值==target；如果到达边界说明不存在该元素，返回false即可（就类似于二叉搜索树）
    //时间复杂度:O(n+m) 空间复杂度:O(1)
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int i = 0;
        int j = matrix[0].length - 1;

        while (i < matrix.length && j>=0) {
            if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] == target) {
                return true;
            }else {
                j--;
            }
        }
        return false;
    }

    /*
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0||matrix[0].length==0) {
            return false;
        }

//        int nx = matrix.length; //行数
        int nx = matrix[0].length; //列数


        if (binarySearch(matrix[0], target) == -1) {

            int left = this.left;
            int right = this.right;
            if (left < nx && left >= 0 && binarySearch(matrix[left], target) != -1) {
                return true;
            }
            if (right < nx && right >= 0 && binarySearch(matrix[right], target) != -1) {
                return true;
            }
            return false;
        }
        return true;
    }
    int binarySearch(int[] nums,int target) {
        int left = 0, right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] == target) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
        this.left = left;
        this.right = right;
        return -1;
    }*/
}
